(* Yoann Padioleau, Iago Abal
 *
 * Copyright (C) 2020-2022 Semgrep Inc.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * version 2.1 as published by the Free Software Foundation, with the
 * special exception on linking described in file LICENSE.
 *
 * This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the file
 * LICENSE for more details.
 *)
open Common
open AST_generic
open Naming_utils
module H = AST_generic_helpers
module Log = Log_naming.Log

(* see error() below *)
let error_report = false

(*****************************************************************************)
(* Prelude *)
(*****************************************************************************)
(* The goal of this module is to resolve names, a.k.a naming or
 * scope resolution, and to do it in a generic way on the generic AST.
 * update: this module is also (ab)used to propagate type information
 * used in semgrep for matching typed metavariables.
 *
 * In a compiler you often have those phases:
 *  - lexing
 *  - parsing
 *  - naming (the goal of this file)
 *  - typing
 *  - intermediate code generation
 *  - optimizing
 *  - ...
 *
 * The goal of the naming phase is to simplify following phases by having
 * each use of an entity clearly linked to its definition. For example,
 * when you see in the AST the use of the identifier 'a', this 'a'
 * could reference a local variable, or a parameter, or a global,
 * or a global defined in another module but imported in the current
 * namespace, or a variable defined in a nested block that "shadows" an
 * enclosing variable with the same name.
 * By resolving once and for all all uses of an entity to its definition,
 * for example by renaming some shadow variables (see AST_generic.gensym),
 * we simpify further phases, which don't have to maintain anymore a
 * complex environment to deal with scoping issues
 * (see the essence Of Python paper "Python: The Full Monty" where they
 * show that even complex IDEs still do not correctly handle Python
 * scoping rules and perform wrong renaming refactorings).
 *
 * Resolving names by tagging identifiers is also useful for
 * codemap/efuns to colorize identifiers (locals, params, globals, unknowns)
 * differently.
 *
 * alternatives:
 *  - CURRENT: generic naming and use of a 'ref resolved_name' to annotate
 *    the generic AST. Note that the use of a ref that can be shared with
 *    the lang-specific AST (e.g., ast_go.ml) allows tools like codemap/efuns
 *    to benefit from the generic naming analysis while still caring only
 *    about the lang-specific AST (even though we may want at some point
 *    to have a generic highlighter).
 *  - define a separate type for a named ast, e.g., nast.ml (as done in
 *    hack/skip) instead of modifying refs, with a unique identifier
 *    for each entity. However, this is tedious to
 *    write as both types are almost identical (maybe a functor could help,
 *    or a generic aast type as in recent hack code). Moreover, this is really
 *    useful for complex global analysis (or at least semi-global as in
 *    OCaml where you still need to open many .cmi when you locally type a .ml)
 *    such as typing where we want to resolve every use of a global.
 *    For semgrep, where we might for quite some time restrict ourselves to
 *    local analysis, maybe the ref implementation technique is good enough.
 *  - implement a resolve_xxx.ml for each language instead of doing it
 *    on the generic AST. That is what I was doing previously, which
 *    has some advantages (some language-specific constructs that introduce
 *    new variables, for example Python comprehensions, are hard to analyze
 *    once converted to the generic AST because they are under an
 *    Other_xxx category)
 *    update: actually comprehensions are now a regular AST element
 *    However, there's potentially lots of code
 *    duplication for each language and it's easy for a language to fall
 *    behind.
 *    A nice compromise might be to do most of the work in naming_ast.ml
 *    but still have lang-specific resolve_xxx.ml to tag special
 *    constructs that override what naming_ast.ml would do.
 *    See set_resolved()
 *
 * TODO:
 *  - generalize the original "resolvers":
 *    * resolve_go.ml
 *    * resolve_python.ml
 *    * ast_js_build.ml
 *    * check_variables_cpp.ml
 *    * check_variables_php.ml
 *  - introduce extra VarDef for languages that do not have them like
 *    Python/PHP where the first use is a def (which in turn requires
 *    special construct like 'global' or 'nonlocal' to disable this).
 *  - go:
 *    * handle DShortVars and Foreach local vars, DMethod receiver parameter,
 *      and TypeName for new types
 *    * in theory if/for/switch with their init declare new scope, as well
 *      as Block
 *    * should do first pass to get all toplevel decl as you can use
 *      forward ref in Go
 *  - get rid of the original "resolvers":
 *    * resolve_xxx.ml
 *    * ast_js_build.ml
 *    * check_variables_xxx.ml
 *  - get rid of or unify scope_code.ml, scope_php.ml, and
 *    ast_generic.resolved_name
 *  - resolve also types! in java if you import org.foo.Bar then later
 *    you can simply use Bar x; for a type, but we don't currently resolve
 *    those.
 *
 * history:
 *  - PHP deadcode detector with global analysis and global code database
 *  - local name resolution for PHP and C/C++ in check_variables_cpp.ml and
 *    check_variables_php.ml for codemap semantic highlighting of identifiers
 *    (mainly local vs params vs globals vs unknown) and for checkModule
 *    (scheck ancestor). Use of a ref for C/C++.
 *  - graph_code_xxx.ml global name resolution for PHP, then Java,
 *    then ML, then ML via cmt, then Clang ASTs, then C, then Javascript
 *  - separate named AST (nast.ml) and naming phase for Hack
 *  - local name resolution for code highlighting for Javascript, then Python
 *    to better colorize identifiers in codemap/efuns, but separate from
 *    a variable checker (resolve_xxx.ml instead of check_variables_xxx.ml)
 *  - AST generic and its resolved_name ref
 *  - simple resolve_python.ml with variable and import resolution
 *  - separate resolve_go.ml with import resolution
 *  - try to unify those resolvers in one file, naming_ast.ml
 *  - resolve names for OCaml constructs and factorize name resolution
 *    in better 'name' type and 'kname' hook.
 *)

(* Performing normalization of types e.g. A | B => Union[A, B] in
   Python. This hook will be linked to Type_aliasing.ml *)
let pro_hook_normalize_ast_generic_type = ref None

(*****************************************************************************)
(* Scope *)
(*****************************************************************************)

(* this includes the "single unique id" (sid) *)
type resolved_name = AST_generic.resolved_name

type scope_info = {
  (* variable kind and sid *)
  entname : resolved_name;
  (* variable type, if known *)
  enttype : type_ option;
}

type scope = (string, scope_info) Assoc.t

type scopes = {
  global : scope ref;
  (* function, nested blocks, nested functions (lambdas) *)
  blocks : scope list ref;
  (* useful for python, kind of global scope but for entities *)
  imported : scope ref;
      (* todo?
       * - class? right now we abuse EnclosedVar in resolved_name_kind.
       * - function? for 'var' in JS
       *)
}

let default_scopes () = { global = ref []; blocks = ref []; imported = ref [] }

(* because we use a Visitor instead of a clean recursive
 * function passing down an environment, we need to emulate a scoped
 * environment by using save_excursion.
 *)

let with_new_function_scope params scopes f =
  Common.save_excursion_unsafe scopes.blocks (params :: !(scopes.blocks)) f

let with_new_block_scope scopes f =
  Common.save_excursion_unsafe scopes.blocks ([] :: !(scopes.blocks)) f

let add_ident_current_scope (s, _) resolved scopes =
  match !(scopes.blocks) with
  | [] -> scopes.global := (s, resolved) :: !(scopes.global)
  | xs :: xxs -> scopes.blocks := ((s, resolved) :: xs) :: xxs

(* for Python *)
let add_ident_imported_scope (s, _) resolved scopes =
  scopes.imported := (s, resolved) :: !(scopes.imported)

let add_ident_global_scope (s, _) resolved scopes =
  scopes.global := (s, resolved) :: !(scopes.global)

(* for JS 'var' *)
let _add_ident_function_scope _id _resolved _scopes = raise Todo
let untyped_ent name = { entname = name; enttype = None }

(* see also lookup_scope_opt below taking as a parameter the environment *)
let rec lookup ?(class_attr = false) s xxs =
  match xxs with
  | [] -> None
  | xs :: xxs -> (
      match List.assoc_opt s xs with
      | None -> lookup ~class_attr s xxs
      | Some res when class_attr -> (
          match res.entname with
          | EnclosedVar, _ -> Some res
          (* If we are looking for a class attribute, and we encounter something
           * else, e.g. a 'Parameter', then we should keep looking. This happens
           * e.g. in this situation:
           *
           *     class Test {
           *         private int x;
           *         public void test(int x) {
           *             foo(this.x);           // <--- this.x is not shadowed by
           *                                    //      the `x` parameter.
           *         }
           *     }
           *)
          | __else__ -> lookup ~class_attr s xxs)
      | Some res -> Some res)

(* for Python, PHP *)
let lookup_global_scope (s, _) scopes = lookup s [ !(scopes.global) ]

(* for Python, PHP *)
let lookup_nonlocal_scope id scopes =
  let s, tok = id in
  match !(scopes.blocks) with
  | _ :: xxs -> lookup s xxs
  | [] ->
      let _ = error tok "no outerscope" in
      None

let has_block_scope (lang : Lang.t) =
  match lang with
  (* These languages don't have block scope *)
  | Ruby
  | Python
  | Php ->
      false
  | _js_ when Lang.is_js lang -> false
  (* The rest do. *)
  | _else_ -> true

(*****************************************************************************)
(* Environment *)
(*****************************************************************************)
type context =
  | AtToplevel
  | InClass
  (* separate InMethod? InLambda? just look for InFunction::InClass::_ *)
  | InFunction

type env = {
  ctx : context list ref;
  (* handle locals/params/globals, block vas, enclosed vars (closures).
   * handle also basic typing information now for Java/Go.
   *)
  names : scopes;
  in_lvalue : bool ref;
  in_type : bool ref;
  lang : Lang.t;
}

let default_env lang =
  {
    ctx = ref [ AtToplevel ];
    names = default_scopes ();
    in_lvalue = ref false;
    in_type = ref false;
    lang;
  }

(*****************************************************************************)
(* Environment Helpers *)
(*****************************************************************************)

let with_new_context ctx env f =
  Common.save_excursion_unsafe env.ctx (ctx :: !(env.ctx)) f

let top_context env =
  match !(env.ctx) with
  | [] -> raise Impossible
  | x :: _xs -> x

let set_resolved env id_info x =
  (* TODO? maybe do it only if we have something better than what the
   * lang-specific resolved found?
   *)
  id_info.id_resolved := Some x.entname;
  let normalize_type =
    match !pro_hook_normalize_ast_generic_type with
    | Some f -> f
    | None -> fun _ x -> x
  in
  (* This is defensive programming against the possibility of introducing
   * cycles in the AST.
   * Indeed, when we are inside a type, especially in  (OtherType (OT_Expr)),
   * we don't want set_resolved to set the type on some Id because
   * this could lead to cycle in the AST because of id_type
   * that will reference a type, that could containi an OT_Expr, containing
   * an Id, that could contain the same id_type, and so on.
   * See tests/naming/python/shadow_name_type.py for a patological example
   * See also tests/rust/parsing/misc_recursion.rs for another example.
   *)
  if not !(env.in_type) then
    id_info.id_type := x.enttype |> Option.map (normalize_type env.lang)

(* accessors *)
let lookup_scope_opt ?(class_attr = false) (s, _) env =
  let scopes = env.names in

  let actual_scopes =
    match !(scopes.blocks) with
    | [] -> [ !(scopes.global); !(scopes.imported) ]
    | xs :: xxs -> (
        match env.lang with
        | Lang.Python ->
            if
              !(env.in_lvalue)
              (* just look current scope! no access to nested scopes or global *)
            then [ xs; !(scopes.imported) ]
            else [ xs ] @ xxs @ [ !(scopes.global); !(scopes.imported) ]
        (* | Lang.Php ->
             (* just look current scope! no access to nested scopes or global *)
             [xs;                            !(scopes.imported)]
        *)
        | _ -> [ xs ] @ xxs @ [ !(scopes.global); !(scopes.imported) ])
  in
  lookup ~class_attr s actual_scopes

(*****************************************************************************)
(* Error management *)
(*****************************************************************************)

let error tok s =
  if error_report then raise (Parsing_error.Other_error (s, tok))
  else Log.err (fun m -> m "%s at %s" s (Tok.stringpos_of_tok tok))

(*****************************************************************************)
(* Typing Helpers *)
(*****************************************************************************)

(* should use TyBuiltin instead? *)
let make_type type_string tok =
  Some (TyN (Id ((type_string, tok), empty_id_info ())) |> AST_generic.t)

(* This is only one part of the code to handle typed metavariables. Here
 * the goal is to help is setting the id_info.id_type for a few
 * identifiers in VarDef or Assign. Then, Generic_vs_generic.m_compatible_type
 * can leverage the info.
 *)
let rec get_resolved_type lang (vinit, vtype) =
  match vtype with
  | None
  | Some { t = TyAny _; _ } -> (
      (* Use proprietary type inference, if applicable.
         This needs to be here while we still use `Naming_AST` for intrafile
         scans, as opposed to `Naming_SAST`.
      *)
      let pro_type =
        match (!Typing.pro_hook_type_of_expr, vinit) with
        | Some f, Some e ->
            let* type_ = f lang e in
            Type.to_ast_generic_type_ lang (fun name _alts -> name) type_
        | _ -> None
      in
      match pro_type with
      | Some x -> Some x
      | None -> (
          (* Currently these vary between languages *)
          (* Alternative is to define a TyInt, TyBool, etc. in the generic AST *)
          (* so this would be more portable across languages *)
          match vinit with
          | Some { e = L (Bool (_, tok)); _ } -> make_type "bool" tok
          | Some { e = L (Int (_, tok)); _ } -> make_type "int" tok
          | Some { e = L (Float (_, tok)); _ } -> make_type "float" tok
          | Some { e = L (Char (_, tok)); _ } -> make_type "char" tok
          | Some { e = L (String (_, (_, tok), _)); _ } ->
              let string_str =
                match lang with
                | Lang.Go -> "str"
                | Lang.Js
                | Lang.Ts ->
                    "string"
                | _ -> "string"
              in
              make_type string_str tok
          | Some { e = L (Regexp ((_, (_, tok), _), _)); _ } ->
              make_type "regexp" tok
          | Some { e = RegexpTemplate ((l, _fragments, _r), _); _ } ->
              (* TODO: need proper location instead of just the opening '/'? *)
              make_type "regexp" l
          | Some { e = L (Unit tok); _ } -> make_type "unit" tok
          | Some { e = L (Null tok); _ } -> make_type "null" tok
          | Some { e = L (Imag (_, tok)); _ } -> make_type "imag" tok
          (* alt: lookup id in env to get its type, which would be cleaner *)
          | Some { e = N (Id (_, { id_type; _ })); _ } -> !id_type
          | Some { e = New (_, tp, _, (_, _, _)); _ } -> Some tp
          | Some { e = Ref (tok, exp); _ } ->
              Option.bind
                (get_resolved_type lang (Some exp, None))
                (fun x -> Some (t @@ TyPointer (tok, x)))
          | _ -> None))
  | Some _ -> vtype

(*****************************************************************************)
(* Other Helpers *)
(*****************************************************************************)

let is_resolvable_name_ctx env lang =
  match top_context env with
  | AtToplevel
  | InFunction ->
      true
  | InClass -> (
      match lang with
      (* true for Java so that we can type class fields *)
      | Lang.Java
      | Lang.Kotlin
      | Lang.Apex
      | Lang.Csharp
      (* true for JS/TS so that we can resolve class methods *)
      | Lang.Js
      | Lang.Ts
      | Lang.Php
      | Lang.Scala ->
          true
      | _ -> false)

let resolved_name_kind env lang =
  match top_context env with
  | AtToplevel -> Global
  | InFunction -> LocalVar
  | InClass -> (
      match lang with
      (* true for Java so that we can type class fields.
       * alt: use a different scope.class?
       *)
      | Lang.Java
      | Lang.Kotlin
      | Lang.Apex
      | Lang.Csharp
      (* true for JS/TS to resolve class methods. *)
      | Lang.Js
      | Lang.Ts
      | Lang.Php
      | Lang.Scala ->
          EnclosedVar
      | _ -> raise Impossible)

(* !also set the id_info of the parameter as a side effect! *)
let params_of_parameters env params : scope =
  params |> Tok.unbracket
  |> List_.filter_map (function
       | Param { pname = Some id; pinfo = id_info; ptype = typ; _ } ->
           let sid = SId.mk () in
           let resolved = { entname = (Parameter, sid); enttype = typ } in
           set_resolved env id_info resolved;
           Some (H.str_of_ident id, resolved)
       | _ -> None)

let js_get_angular_constructor_args env attrs defs =
  let is_injectable =
    List.exists
      (function
        | NamedAttr (_, Id ((s, _), _), _) when is_js_angular_decorator s ->
            true
        | _ -> false)
      attrs
  in
  defs
  |> List_.filter_map (function
       | {
           s =
             DefStmt
               ( { name = EN (Id (("constructor", _), _)); _ },
                 FuncDef { fparams; _ } );
           _;
         }
         when is_injectable ->
           Some (params_of_parameters env fparams)
       | _ -> None)
  |> List_.flatten

let declare_var env lang id id_info ~explicit vinit vtype =
  let sid = SId.mk () in
  (* for the type, we use the (optional) type in vtype, or, if we can infer
   * the type of the expression vinit (literal or id), we use that as a type
   * useful when the type is not given, e.g. in Go: `var x = 2` *)
  let resolved_type = get_resolved_type lang (vinit, vtype) in
  let name_kind, add_ident_to_its_scope =
    (* In JS/TS an assignment to a variable that has not been
     * previously declared will implicitly create a property on
     * the *global* object. *)
    if Lang.is_js lang && not explicit then (Global, add_ident_global_scope)
    else (resolved_name_kind env lang, add_ident_current_scope)
  in
  let resolved = { entname = (name_kind, sid); enttype = resolved_type } in
  add_ident_to_its_scope id resolved env.names;
  set_resolved env id_info resolved

let assign_implicitly_declares lang =
  lang =*= Lang.Python || lang =*= Lang.Ruby || lang =*= Lang.Php
  || Lang.is_js lang

(*****************************************************************************)
(* Entry point *)
(*****************************************************************************)

class ['self] resolve_visitor env lang =
  object (self : 'self)
    inherit [_] AST_generic.iter_no_id_info as super

    val env = env
    val lang = lang

    (* ---------- *)
    (* !the defs! *)
    (* ---------- *)
    method! visit_function_definition venv x =
      (* todo: add the function as a Global. In fact we should do a first
       * pass for some languages to add all of them first, because
       * Go for example allow the use of forward function reference
       * (no need to declarare prototype and forward decls as in C).
       *)
      let new_params = params_of_parameters env x.fparams in
      with_new_context InFunction env (fun () ->
          with_new_function_scope new_params env.names (fun () ->
              (* todo: actually we should first go inside x.fparams.ptype
               * without the new_params (this would also prevent cycle if
               * a parameter name is the same than type name used in ptype
               * (see tests/naming/python/shadow_name_type.py) *)
              super#visit_function_definition venv x))

    method! visit_definition venv x =
      match x with
     | { attrs; _ } as entity, ClassDef c ->
          let class_params = params_of_parameters env c.cparams in
          with_new_context InClass env (fun () ->
              let special_class_params =
                if Lang.is_js lang then
                  let _, fields, _ = c.cbody in
                  js_get_angular_constructor_args env attrs
                    (List_.map (fun (F x) -> x) fields)
                else []
              in
              (* TODO? Maybe we need a `with_new_class_scope`. For now, abusing `with_new_function_scope`. *)
              with_new_function_scope (special_class_params @ class_params)
                env.names (fun () ->
                  self#visit_entity venv entity;
                  self#visit_class_definition venv (H.reorder_fields_in_class_definition c)))
      (* `const x = require('y');` (or var, or let)
       *
       * JS: This is a CommonJS import, popularized before ES6 standardized
       * imports/exports. *)
      | ( { name = EN (Id (id, id_info)); _ },
          VarDef
            {
              vinit =
                Some
                  {
                    e =
                      Call
                        ( { e = IdSpecial (Require, _); _ },
                          (_, [ Arg { e = L (String (_, file, _)); _ } ], _)
                        );
                    _;
                  };
              _;
            } )
        when lang =*= Lang.Js || lang =*= Lang.Ts ->
          let sid = SId.mk () in
          let canonical = dotted_to_canonical [ file ] in
          let resolved = untyped_ent (ImportedModule canonical, sid) in
          set_resolved env id_info resolved;
          add_ident_current_scope id resolved env.names
      (* `const {x, y} = require('z');` (or var, or let)
       *
       * JS: This is a CommonJS import, popularized before ES6 standardized
       * imports/exports. *)
      | ( { name = EN (Id ((id_str, _), _)); _ },
          VarDef
            {
              vinit =
                Some
                  {
                    e =
                      Assign
                        ( { e = Record (_, fields, _); _ },
                          _,
                          {
                            e =
                              Call
                                ( { e = IdSpecial (Require, _); _ },
                                  ( _,
                                    [ Arg { e = L (String (_, file, _)); _ } ],
                                    _ ) );
                            _;
                          } );
                    _;
                  };
              _;
            } )
        when id_str = special_multivardef_pattern
             && (lang =*= Lang.Js || lang =*= Lang.Ts) ->
          List.iter
            (function
              | F
                  {
                    s =
                      DefStmt
                        ( {
                            name = EN (Id (imported_id, _imported_id_info));
                            attrs = [];
                            tparams = None;
                          },
                          FieldDefColon
                            {
                              vinit =
                                Some
                                  { e = N (Id (local_id, local_id_info)); _ };
                              _;
                            } );
                    _;
                  } ->
                  let sid = SId.mk () in
                  let canonical = dotted_to_canonical [ file; imported_id ] in
                  let resolved =
                    untyped_ent (ImportedEntity canonical, sid)
                  in
                  set_resolved env local_id_info resolved;
                  add_ident_current_scope local_id resolved env.names
                  (* TODO handle nested destructuring? *)
              | _ -> ())
            fields
      (* In Rust, the left-hand side (lhs) of the let variable definition is
       * parsed as a pattern.
       * TODO handle more cases than just the simple identifier pattern. *)
      | ( { name = EPattern (PatId (id, id_info)); _ },
          VarDef { vinit; vtype; vtok = _ } )
      | { name = EN (Id (id, id_info)); _ }, VarDef { vinit; vtype; vtok = _ }
      (* note that some languages such as Python do not have VarDef
       * construct
       * todo? should add those somewhere instead of in_lvalue detection? *)
        when is_resolvable_name_ctx env lang ->
          (* Need to visit expressions first so that the id_type of
           * an id gets populated, e.g.
           * if we do var a = 3, then var b = a, we want to propagate the
           * type of a.
           * alt: do the lookup type in resolved_type
           *)
          super#visit_definition venv x;
          declare_var env lang id id_info ~explicit:true vinit vtype
      | { name = EN (Id (id, id_info)); _ }, FuncDef _
        when is_resolvable_name_ctx env lang ->
          (match lang with
          (* We restrict function-name resolution to JS/TS.
           *
           * Note that this causes problems with Python rule/test:
           *
           *     semgrep-rules/python/flask/correctness/same-handler-name.yaml
           *
           * This rule tries to match two different functions using the same
           * meta-variable. This works when the function names are not resolved,
           * but breaks when each function gets a unique sid.
           *
           * Function-name resolution is useful for interprocedural analysis,
           * feature that was requested by JS/TS users, see:
           *
           *     https://github.com/semgrep/semgrep/issues/2787.
           *)
          | Lang.Js
          | Lang.Ts ->
              let sid = SId.mk () in
              let resolved = untyped_ent (resolved_name_kind env lang, sid) in
              (* Previously we tried using add_ident_current_scope, but this
               * shadowed imported function names which are added to the
               * "imported" scope (globals/block scope is looked up first)
               * even when the import statement comes after...
               * This broke the following test:
               *
               *     semgrep-rules/python/django/security/audit/raw-query.py
               *
               * For now we add function names also to the "imported" scope...
               * but do we need a special scope for imported functions?
               *)
              add_ident_imported_scope id resolved env.names;
              set_resolved env id_info resolved
          | ___else___ -> ());
          super#visit_definition venv x
      | { name = EN (Id (id, id_info)); _ }, UseOuterDecl tok ->
          let s = Tok.content_of_tok tok in
          let flookup =
            match s with
            | "global" -> lookup_global_scope
            | "nonlocal" -> lookup_nonlocal_scope
            | _ ->
                error tok (spf "unrecognized UseOuterDecl directive: %s" s);
                lookup_global_scope
          in
          (match flookup id env.names with
          | Some resolved ->
              set_resolved env id_info resolved;
              add_ident_current_scope id resolved env.names
          | None ->
              error tok
                (spf "could not find '%s' for directive %s"
                   (H.str_of_ident id) s));
          super#visit_definition venv x
      (* module L = List, in OCaml *)
      | ( { name = EN (Id (id, id_info)); _ },
          ModuleDef { mbody = ModuleAlias xs } ) ->
          (* similar to the ImportAs case *)
          let sid = SId.mk () in
          let canonical = dotted_to_canonical xs in
          let resolved = untyped_ent (ImportedModule canonical, sid) in
          set_resolved env id_info resolved;
          (* difference with ImportAs, we add in local scope in OCaml *)
          add_ident_current_scope id resolved env.names;
          super#visit_definition venv x
      | ( { name = EN (Id (id, id_info)); _ },
          MacroDef
            { macroparams = []; macrobody = [ E ({ e = L _; _ } as e) ] } ) ->
          declare_var env lang id id_info ~explicit:true (Some e) None;
          super#visit_definition venv x
      (* general case, just recurse *)
      | _ -> super#visit_definition venv x

    (* sgrep: the import aliases *)
    method! visit_directive venv x =
      (match x.d with
      | ImportFrom (_, DottedName xs, imported_names) ->
          List.iter
            (function
              | id, Some (alias, id_info) ->
                  (* for python *)
                  let sid = SId.mk () in
                  let canonical = dotted_to_canonical (xs @ [ id ]) in
                  let resolved =
                    untyped_ent (ImportedEntity canonical, sid)
                  in
                  set_resolved env id_info resolved;
                  add_ident_imported_scope alias resolved env.names
              | id, None ->
                  (* for python *)
                  let sid = SId.mk () in
                  let canonical = dotted_to_canonical (xs @ [ id ]) in
                  let resolved =
                    untyped_ent (ImportedEntity canonical, sid)
                  in
                  add_ident_imported_scope id resolved env.names)
            imported_names
      | ImportFrom (_, FileName (s, tok), imported_names) ->
          List.iter
            (function
              | id, None
                when Lang.is_js lang && fst id <> Ast_js.default_entity ->
                  (* for JS we consider import { x } from 'a/b/foo' as foo.x.
                   * Note that we guard this code with is_js lang, because Python
                   * uses also Filename in 'from ...conf import x'.
                   *)
                  let sid = SId.mk () in
                  let _, b, _ = Filename_.dbe_of_filename_noext_ok s in
                  let base = (b, tok) in
                  let canonical = dotted_to_canonical [ base; id ] in
                  let resolved =
                    untyped_ent (ImportedEntity canonical, sid)
                  in
                  add_ident_imported_scope id resolved env.names
              | id, Some (alias, id_info)
                when Lang.is_js lang && fst id <> Ast_js.default_entity ->
                  (* for JS *)
                  let sid = SId.mk () in
                  let _, b, _ = Filename_.dbe_of_filename_noext_ok s in
                  let base = (b, tok) in
                  let canonical = dotted_to_canonical [ base; id ] in
                  let resolved =
                    untyped_ent (ImportedEntity canonical, sid)
                  in
                  set_resolved env id_info resolved;
                  add_ident_imported_scope alias resolved env.names
              | _ -> ())
            imported_names
      | ImportAs (_, DottedName xs, Some (alias, id_info)) ->
          (* for python *)
          let sid = SId.mk () in
          let canonical = dotted_to_canonical xs in
          let resolved = untyped_ent (ImportedModule canonical, sid) in
          set_resolved env id_info resolved;
          add_ident_imported_scope alias resolved env.names
      | ImportAs (_, FileName (s, tok), Some (alias, id_info)) ->
          (* for Go *)
          let sid = SId.mk () in
          let pkgname = go_package_alias s in
          let base = (pkgname, tok) in
          let canonical = dotted_to_canonical [ base ] in
          let resolved = untyped_ent (ImportedModule canonical, sid) in
          set_resolved env id_info resolved;
          add_ident_imported_scope alias resolved env.names
      | _ -> ());
      super#visit_directive venv x

    method! visit_catch venv x =
      let _t, exn, _st = x in
      (match exn with
      (* TODO: we should create a new block scope *)
      | CatchParam { pname = Some id; pinfo = id_info; _ }
        when is_resolvable_name_ctx env lang ->
          declare_var env lang id id_info ~explicit:true None None
      | _ -> ());
      super#visit_catch venv x

    method! visit_pattern venv x =
      match x with
      | PatId (id, id_info) when is_resolvable_name_ctx env lang ->
          (* todo: in Python it does not necessarily introduce
           * a newvar if the ID was already declared before.
           * Also inside a PatAs(PatId x,b), the 'x' is actually
           * the name of a class, not a newly introduced local.
           *)
          declare_var env lang id id_info ~explicit:true None None;
          super#visit_pattern venv x
      | PatTyped (PatId (id, id_info), ty)
        when is_resolvable_name_ctx env lang ->
          declare_var env lang id id_info ~explicit:true None (Some ty)
      (* do not recurse here, we don't want the PatId case above
       * to overwrite the job done here
       *)
      | PatTyped (pattern, ty) when Lang.is_js lang ->
          Common.save_excursion_unsafe env.in_lvalue true (fun () ->
              super#visit_type_ venv ty);
          super#visit_pattern venv pattern
      (* This is used for Ts in the case of typed patterns with records.
       * For example in a fuction like: 
       *  function ({foo} :{foo:foo_type}){}
       * we need to make sure we do it safely for types otherwise they will
       * be put in the stack. see the test rules/ts_type
       *)
      | OtherPat _
      (* This interacts badly with implicit JS/TS declarations. It causes
       * `foo` in `function f({ foo }) { ... }` to be resolved as a global
       * variable, which in turn affects semgrep-rule _react-props-in-state_.
       * This when-clause achieves the previous behavior of leaving `foo`
       * unresolved. *)
      (* TODO: We should fix the AST of JS/TS so those `f({foo})` patterns do
       * not show as regular variables. *)
        when not (Lang.is_js lang) ->
          Common.save_excursion_unsafe env.in_lvalue true (fun () ->
              super#visit_pattern venv x)
      | _ -> super#visit_pattern venv x

    (* ---------- *)
    (* !the uses! *)
    (* ---------- *)
    (* kname will resolve names for Constructor/PatConstructor/NamedAttr/TyN
     * and maybe more. For expressions, we do something special for N (Id)
     * in kexpr do deal with languages where the first occurence of an
     * Id could be a declaration.
     *)
    method! visit_name venv x =
      match x with
      | Id (id, id_info) -> (
          if
            (* Avoid overwriting 'id_resolved'.
             * THINK: Maybe log something if we were going to overwrite ? *)
            Option.is_none !(id_info.id_resolved)
          then
            match lookup_scope_opt id env with
            | Some resolved ->
                (* name resolution *)
                set_resolved env id_info resolved
            | _ -> ())
      | IdQualified
          {
            name_last = id, None;
            name_middle;
            name_info = id_info;
            name_top = None;
          } ->
          (match name_middle with
          | Some (QDots ((m, None) :: rest_of_middle)) -> (
              match lookup_scope_opt m env with
              (* Resolve modules for OCaml *)
              | Some { entname = ImportedModule xs, _sidm; _ }
              (* Resolve classes for use in typed metavars (Java) *)
              (* Note that we only need to resolve the first name
                 because that is the only one that could be
                 imported *)
              | Some { entname = ImportedEntity xs, _sidm; _ } ->
                  (* The entity is fully qualified, no need for sid *)
                  let sid = SId.unsafe_default in
                  let rest_of_middle = List_.map fst rest_of_middle in
                  let canonical =
                    xs @ dotted_to_canonical (rest_of_middle @ [ id ])
                  in
                  let resolved =
                    untyped_ent (ImportedEntity canonical, sid)
                  in
                  set_resolved env id_info resolved
              | _ -> ())
          | _ -> ());
          super#visit_name venv x
      | IdQualified _ -> ()

    method! visit_expr venv x =
      (* ugly: hack. If we use a classic recursive-with-env visitor,
       * we would not need this *)
      (* TODO now that we do use a classic recursive-with-env visitor,
       * refactor so this isn't needed. *)
      let recurse = ref true in
      (match x.e with
      (* Go: This is `x := E`, a single-variable short variable declaration.
       * When this declaration is legal, and that is when the same variable
       * has not yet been declared in the same scope, it *always* introduces
       * a new variable. (Quoting Go' spec, "redeclaration can only appear
       * in a multi-variable short declaration".)
       * See: https://golang.org/ref/spec#Short_variable_declarations *)
      | AssignOp ({ e = N (Id (id, id_info)); _ }, (Eq, tok), e2)
        when lang =*= Lang.Go
             && Tok.content_of_tok tok = ":="
             && is_resolvable_name_ctx env lang ->
          (* Need to visit the RHS first so that type is populated *)
          (* If we do var a = 3, then var b = a, we want to propagate the type of a *)
          super#visit_expr venv x;
          declare_var env lang id id_info ~explicit:true (Some e2) None;
          recurse := false
      | Assign ({ e = N (Id (id, id_info)); _ }, _, e2)
        when Option.is_none (lookup_scope_opt id env)
             && assign_implicitly_declares lang
             && is_resolvable_name_ctx env lang ->
          (* Need to visit the RHS first so that type is populated *)
          self#visit_expr venv e2;
          declare_var env lang id id_info ~explicit:false (Some e2) None;
          recurse := false
      (* todo: see lrvalue.ml
       * alternative? extra id_info tag?
       *)
      | Assign (e1, _, e2)
      | AssignOp (e1, _, e2) ->
          Common.save_excursion_unsafe env.in_lvalue true (fun () ->
              self#visit_expr venv e1);
          self#visit_expr venv e2;
          recurse := false
      | ArrayAccess (e1, (_, e2, _)) ->
          self#visit_expr venv e1;
          Common.save_excursion_unsafe env.in_lvalue false (fun () ->
              self#visit_expr venv e2);
          recurse := false
      (* specialized kname case when in expr context *)
      | N (Id (id, id_info)) ->
          (match lookup_scope_opt id env with
          | Some resolved ->
              (* name resolution *)
              set_resolved env id_info resolved
          | None ->
              if
                !(env.in_lvalue)
                && assign_implicitly_declares lang
                && is_resolvable_name_ctx env lang
              then
                (* first use of a variable can be a VarDef in some languages *)
                declare_var env lang id id_info ~explicit:false None None
              else
                (* hopefully the lang-specific resolved may have resolved that *)
                (* TODO: this can happen because of in_lvalue bug detection, or
                 * for certain entities like functions or classes which are
                 * currently tagged
                 *)
                let s, tok = id in
                error tok (spf "could not find '%s' in environment" s));
          recurse := false
      | DotAccess
          ({ e = IdSpecial ((This | Self), _); _ }, _, FN (Id (id, id_info)))
        -> (
          match lookup_scope_opt ~class_attr:true id env with
          (* TODO: this is a v0 for doing naming and typing of fields.
           * we should really use a different lookup_scope_class, that
           * would handle shadowing of fields from locals, etc. but it's
           * a start.
           *)
          | Some ({ entname = EnclosedVar, _sid; _ } as resolved) ->
              set_resolved env id_info resolved;
              recurse := false
          | _ ->
              let s, tok = id in
              error tok (spf "could not find '%s' field in environment" s))
      | Comprehension (_op, (_l, (e, xs), _r)) ->
          (* Actually in Python2, no new scope was created, so iterator vars
           * could leak in the outer scope. This was fixed in Python3. *)
          with_new_block_scope env.names (fun () ->
              (* first visit xs, then e *)
              xs |> List.iter (fun x -> self#visit_for_or_if_comp venv x);
              self#visit_expr venv e);
          recurse := false
      | _ -> ());
      if !recurse then super#visit_expr venv x

    method! visit_type_ venv x =
      if !(env.in_type) then super#visit_type_ venv x
      else
        Common.save_excursion_unsafe env.in_type true (fun () ->
            super#visit_type_ venv x)

    (* TODO: support other types of statements that create block scopes. *)
    method! visit_stmt venv x =
      match x.s with
      | If (tok, Cond e, s1, s2_opt) when has_block_scope lang ->
          self#visit_tok venv tok;
          self#visit_expr venv e;
          with_new_block_scope env.names (fun () -> self#visit_stmt venv s1);
          Option.iter
            (fun s2 ->
              with_new_block_scope env.names (fun () ->
                  self#visit_stmt venv s2))
            s2_opt
      | _else_ -> super#visit_stmt venv x
  end
  
let resolve lang prog =
  let env = default_env lang in

  (* coupling: we do similar things in Constant_propagation.ml so if you
   * add a feature here, you might want to add a similar thing over there too.
   *)
  let visitor = new resolve_visitor env lang
  in
  visitor#visit_program () prog;
  ()
[@@profiling]
